#include <stdio.h>

char prime_table[1000005] = {0};
int range_table[1000005];

void prepare() {
    // filter all even primes
    prime_table[0] = prime_table[1] = 1;
    for (int i = 2; i < 1005; (i == 2) ? (i++) : (i += 2)) {
        for (int j = i + i; j < 1000005; j += i) {
            prime_table[j] = 1;
        }
    }
    
    int last_prime = -1;
    int count = 0;
    for (int i = 0; i < 1000004; i++) {
        if (prime_table[i] == 0) {
            if (last_prime != -1) {
                int middle = (last_prime + i) / 2;
                if (prime_table[middle]) {
                    count++;
                    // fill back to middle value as these value are wrong
                    for (int j = middle; j < i; j++) {
                        range_table[j] = count;
                    }
                }
            }
            last_prime = i;
        }
        range_table[i] = count;
    }
}

int main(void) {
    prepare();
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", range_table[b] - range_table[a - 1]);
    }
    return 0;
}
